package week7.intlist;

import java.util.List;

/** 
 * Representeert een lijst getallen die te allen tijde gesorteeerd is.
 * Practicumopdracht Programmeren 1.
 * @author W.Looge & R. Oost
 * @version 1.0
 */
public class SortedIntegerList {
	
	/**
	 * De integerlijst die door deze klasse wordt gebruikt.
	 * @invariant Is altijd een niet-dalende-lijst.
	 */
	private List<Integer> lijst = new IntegerList();
	
    /**
     * Construeert nieuwe, lege <tt>SortedIntegerList</tt>
     * @ensure <tt>this.size() == 0</tt>
     */
    public SortedIntegerList() {}
    
    /**
     * Construeert nieuwe <tt>SortedIntegerList</tt> 
     * op basis van bestaande <tt>IntegerList</tt>.
     * De waarde van de parameter wordt niet veranderd.
     * @param il lijst elementen voor deze <tt>SortedIntegerList</tt>
     * @require <tt>il != null</tt>
     * @ensure result bevat dezelfde elementen als <tt>il</tt>
     */
    public SortedIntegerList(final IntegerList il) {
    	this.lijst = new IntegerList();
        int lengte = il.size();
        
        // forall i:int 0 <= < x : lijst.contains(il.get(i))
        for (int x = 0; x < lengte; x++) {
        	this.add(il.get(x));
        }
    }
    
    // -- Queries ----------------------------------------------------

    /**
     * Bepaalt het aantal elementen van deze <tt>SortedIntegerList</tt>.
     * @return het aantal elementen 
     * @ensure <tt>result >= 0</tt>
     */
    public int size() {
        return this.lijst.size();
    }

    /**
     * Levert het getal op een gegeven index in deze <tt>SortedIntegerList</tt>.
     * @param  i de index van het op te leveren getal
     * @require <tt>0 <= i && i < this.size()</tt>
     * @return het getal op positie <tt>i</tt> 
     * @ensure forall i:int, <tt>0 <= i && i < size()-1</tt>: <tt>get(i) <= get(i+1)</tt>
     */
    public Integer get(int i) {
        return this.lijst.get(i);
    }

    /**
     * Test of een ander object ook een <tt>SortedIntegerList</tt> is,
     * en of de intern bijgehouden lijsten gelijk zijn.
     * @ensure <tt>result == </tt> 
     * forall i:int, <tt>0 <= i && i < size(): this.get(i).equals(obj.get(i))</tt>
     */
    public boolean equals(Object obj) {
    	// Gelijk soort object
    	if(obj instanceof SortedIntegerList) {
    		// Zelfde lijsten
    		SortedIntegerList object = (SortedIntegerList) obj;
    		return this.lijst.equals(object.lijst);
    	} else {
    		// Geef false terug als dit niet waar is
    		return false;
    	}
    }

    /**
     * Zoekt naar een getal in deze <tt>SortedIntegerList</tt>.
     * Levert de index op van het eerste element dat 
     * minstens zo groot is als het gezochte getal.
     * @param val gezochte getal
     * @return index van het eerste element dat niet kleiner is 
     * dan <tt>val</tt>; <br>
     * <tt>this.size()</tt> als alle elementen kleiner zijn 
     * dan <tt>val</tt>
     * @ensure <tt>0 <= result && result <= size() &&
     *             get(0 .. result-1) < val && 
     *             get(result .. size()-1) >= val</tt>
     */
    public int itemIndex(Integer val) {
    	// Filter de mogelijkheden die er net buiten vallen eruit.
        if(lijst.size() == 0 || lijst.get(0) >= val)
        	return 0;			// Kleiner dan of gelijk aan de kleinste
        
        int ondergrens = 0;			   // Laagst mogelijke index
        int bovengrens = lijst.size(); // Hoogst mogelijke index (groter dan de hele lijst)
        
        // lijst.get(ondergrens) < val <= lijst.get(bovengrens+1)
		while (ondergrens < bovengrens) {
			int midden = ondergrens + (bovengrens - ondergrens) / 2; // Voorkom overflow van ondergrens + bovengrens
			if (val <= lijst.get(midden)) {	// Gezochte waarde zit boven midden
				bovengrens = midden;
			} else {						// Gezochte waarde zit onder midden
				ondergrens = midden + 1;
			}
		}
		
        return ondergrens;
    }

    /**
     * Zoekt naar een getal in deze <tt>SortedIntegerList</tt>.
     * @param val gezochte getal
     * @return index van het eerste element dat gelijk is 
     * aan <tt>val</tt>, of -1 als zo'n element er niet is.
     * @ensure <tt>(result == -1 && this</tt> bevat <tt>val</tt> niet<tt>) ||
     *         this.get(result).equals(val)</tt>
     */
    public int indexOf(Integer val) {
        int index = itemIndex(val);
        if(this.get(index).equals(val)) return index;
        return -1;
    }

    /** 
     * Levert een beschrijving op van deze <tt>SortedIntegerList</tt>,
     * op basis van de intern bijgehouden lijst.
     */
    public String toString() {
        return this.lijst.toString();
    }

    // -- Commands ---------------------------------------------------

    /**
     * Voegt een getal toe aan deze <tt>SortedIntegerList</tt>.
     * @param val  het toe te voegen getal
     * @ensure <tt>this.size() == old.size()+1 && 
     * </tt> exists i:int, <tt>0 <= i && i < this.size(): this.get(i).equals(val) &&
     * this.get(0 .. i-1) == old.get(0 .. i-1) &&
     * this.get(i+1 .. size()-1) == old.get(i .. old.size()-1)</tt>
     */
    public void add(Integer val) {
      	// Voeg het element toe op de gevonden index
    	lijst.add(itemIndex(val), val);
	}
      
    /** 
     * Levert een lijst waarin alle getallen kleiner dan een 
     * bepaalde grenswaarde verwijderd zijn.
     * @param  grens de ondergrens van de getallen die behouden blijven
     * @return een kopie van deze lijst, waaruit alle getallen 
     * kleiner dan <tt>grens</tt> verwijderd zijn
     * @ensure <tt>result</tt> bevat alle getallen <tt>g</tt>
     * in <tt>this</tt> zodat <tt>g >= grens</tt>
     */
    public SortedIntegerList verwijderKleinerDan(final Integer grens) {
    	// Vind de index van het laagste element van de nieuwe lijst
    	int index = itemIndex(grens);
    	
    	// Maak de nieuwe lijst
    	SortedIntegerList result = new SortedIntegerList();
    	result.lijst = this.lijst.subList(index, this.lijst.size());
    	return result;
    }
    
    /** 
     * Levert het maximum van de lijst op en het aantal keren
     * dat dit maximum in de lijst voorkomt.
     * Dit tweetal wordt als lijst van Integers teruggegeven. 
     * Het eerste element van de resultaatlijst bevat het maximum. 
     * Het tweede element van de resultaatlijst bevat het aantal keren
     * dat dit maximum voorkomt.
     * @return een lijst met twee getallen.<br> Het eerste getal is het
     *         maximum van de lijst met getallen.<br> Het tweede getal is
     *         het aantal keren dat dit maximum voorkomt. 0 als deze lijst
     *         geen elementen bevat.
     * @ensure <ul>
     *     <li> <tt>result.size() == 2</tt>
     *     <li> <tt>result.get(0) == </tt>maximum van deze lijst
     *     <li> <tt>result.get(1) == </tt>aantal keren dat 
     *                               <tt>result.get(0)</tt> voorkomt</ul>
     */
    public IntegerList maximum() {
    	// Geef een resultaat als deze lijst geen elementen bevat
        if (this.size() == 0) return IntegerList.createIntegerList("[0,0]");
        
        // Vind de resultaten
        int max = this.get(this.size() - 1);
        int count = this.size() - this.indexOf(max);
        
        // Geef het resultaat terug
        IntegerList result = new IntegerList();
        result.add(max);
        result.add(count);
        return result;
    }

    /** 
     * Test of er in deze lijst
     * twee dezelfde getallen voorkomen.
     * @return <tt>true</tt> als deze lijst een paar bevat
     * @ensure <tt>result == </tt>(this bevat een paar)
     */
    public boolean heeftPaar() {
        //return ((IntegerList) lijst).heeftPaar();
    	
    	// forall: x:int 0 <= x < i : lijst.get(x) != lijst.get(x+1)
        for (int i = 0; i < this.size() - 1; i++) {
        	// Vergelijk dit element en het volgende element
        	if(lijst.get(i).equals(lijst.get(i+1))) {
        		return true; // Stop zodra dit element een duplicaat blijkt te zijn.
        	}
        }
        
        // Als er dus geen duplicaten zijn gevonden
        return false;
    }

    /** 
     * Combineert een andere <tt>SortedIntegerList</tt> met deze,
     * en levert de gecombineerde (en gesorteerde) lijst op.
     * De beide inputlijsten worden niet veranderd.
     * @param  sil de lijst die met deze gecombineerd dient te worden
     * @return de combinatie van deze lijst en <tt>sil</tt>,
     * bestaande uit de vereniging van de elementen van de twee lijsten.
     * @ensure <tt>result</tt> is de geordende vereniging van <tt>this</tt>
     * en <tt>sil</tt>
     */
    public SortedIntegerList voegSamen(final SortedIntegerList sil) {
        if (sil == null) return this; // Vang sil == null op
        
        // Initialiseer variabelen
        // De waarden zullen worden toegevoegd aan een IntegerList waarvan later een SortedIntegerList wordt gemaakt.
        // Dit is alleen vanwege de inefficientie van de add methode van een SortedIntegerList.
        IntegerList result = new IntegerList();
        // Dit zijn de lengtes van de twee lijsten.
        int lengte1 = this.size();
        int lengte2 = sil.size();
        // Deze pointers geven aan welk element op elke lijst momenteel wordt verwerkt.
        int pointer1 = 0;
        int pointer2 = 0;
        
        // forall i:int 0 <= i < result.size()-1 : result.get(i) <= result.get(i+1)									Altijd stijgend
        // forall i:int 0 <= i < result.size() : lijst.contains(result.get(i)) || sil.contains(result.get(i))		Elk element moet ergens vandaan komen
        while(pointer1 < lengte1 && pointer2 < lengte2) { // Ga net zo lang door totdat 1 van de twee lijsten af is
        	
        	Integer element1 = this.get(pointer1);
        	Integer element2 = sil.get(pointer2);
        	
        	// Bepaal het kleinste element en voeg dat toe aan result
        	if (element1 < element2) {
        		result.add(element1);
        		pointer1++;
        	} else {
        		result.add(element2);
        		pointer2++;
        	}
        }
        
        // Vind welke lijst nog niet af is, en voeg de laatste elementen toe
        if(pointer1 == lengte1) {
        	// Alle overige elementen van de gegeven lijst worden toegevoegd.
        	// forall i:int 0 <= i < x : result.contains(sil.get(i))
        	for(int x = pointer2; x < lengte2; x++) {
        		result.add(sil.get(x));
        	}
        } else {
        	// Alle overige elementen van deze lijst worden toegevoegd.
        	// forall i:int 0 <= i < x : result.contains(lijst.get(i))
        	for(int x = pointer1; x < lengte1; x++) {
        		result.add(this.get(x));
        	}
        }
        
        // Geef het resultaat terug als SortedIntegerList
        SortedIntegerList res = new SortedIntegerList();
        res.lijst = result;
        return res;
    }
}
